//
//  TopKFrequent.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/9/7.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  347. 前 K 个高频元素

import UIKit

/*
 347. 前 K 个高频元素
 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

 示例 1:

 输入: nums = [1,1,1,2,2,3], k = 2
 输出: [1,2]
 示例 2:

 输入: nums = [1], k = 1
 输出: [1]
  

 提示：

 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
 你可以按任意顺序返回答案。
 */

class TopKFrequent: NSObject {
    
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        
        //先构建哈希表  key:数字  value:数字出现的次数
        var numHash:[Int:Int] = [:]
        for num in nums{
            if numHash[num] == nil{
                numHash[num] = 1
            }else{
                numHash[num] = numHash[num]! + 1
            }
        }
        
        //使用桶，数组下标表示出现次数，value中保存数组中的元素
        var bucket:[[Int]] = [[Int]](repeating: [Int](), count: nums.count+1)
        for (key,value) in numHash {
            bucket[value].append(key)
        }
        
        //从后往前拿结果
        var result:[Int] = [Int]()
        for index in (0 ... bucket.count-1).reversed(){
            if result.count < k {
                if bucket[index].count != 0{
                    result += bucket[index]
                }
            }else{
                return result
            }
        }
        
        return result
    }
    

    //求前k大，用小顶堆；求前k小，用大顶堆
}
